package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href='https://leetcode.cn/problems/asteroid-collision/'>小行星碰撞(Asteroid Collision)</a>
 * <p>给定一个整数数组 asteroids，表示在同一行的小行星。</p>
 * <p>对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。</p>
 * <p>找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：asteroids = [5,10,-5]
 *      输出：[5,10]
 *      解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
 *
 * 示例 2：
 *      输入：asteroids = [8,-8]
 *      输出：[]
 *      解释：8 和 -8 碰撞后，两者都发生爆炸。
 *
 * 示例 3：
 *      输入：asteroids = [10,2,-5]
 *      输出：[10]
 *      解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>2 <= asteroids.length <= 10^4</li>
 *     <li>-1000 <= asteroids[i] <= 1000</li>
 *     <li>asteroids[i] != 0</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/13 10:43
 */
public class LC0735AsteroidCollision_M {

    static class Solution {

        public int[] asteroidCollision(int[] asteroids) {
            Deque<Integer> stack = new ArrayDeque<>();
            for (int asteroid : asteroids) {
                // 假设当前行星存活
                boolean ifAlive = true;
                // 只有在之前的行星向右，当前的行星向左的情况下，才有可能发生爆炸的情况
                while (ifAlive && asteroid < 0 && !stack.isEmpty() && stack.peekLast() > 0) {
                    // 栈顶行星一定大于0
                    // 当前行星一定小于0
                    int absAsteroid = -asteroid;
                    // 1.当前行星的绝对值，小于等于栈顶行星的值，当前行星爆炸
                    if (absAsteroid <= stack.peekLast()) {
                        ifAlive = false;
                    }
                    // 2.当前行星的绝对值，大于等于栈顶行星的值，当前行星爆炸
                    if (absAsteroid >= stack.peekLast()) {
                        stack.pollLast();
                    }
                }
                if (ifAlive) {
                    stack.offerLast(asteroid);
                }
            }
            int[] res = new int[stack.size()];
            for (int i = res.length - 1; i >= 0 && !stack.isEmpty(); i--) {
                res[i] = stack.pollLast();
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.asteroidCollision(new int[]{5, 10, -5}));
        Printer.printArrayInt(solution.asteroidCollision(new int[]{10, 5, -5}));
        Printer.printArrayInt(solution.asteroidCollision(new int[]{5, -5}));
        Printer.printArrayInt(solution.asteroidCollision(new int[]{10, 2, -5}));
        Printer.printArrayInt(solution.asteroidCollision(new int[]{-2,-1,1,2}));
    }
}
